package org.hot100_1;

import org.leetcode.TreeNode;

public class leetcode40 {
    //543
    int res =1;
    public int diameterOfBinaryTree(TreeNode root) {

        getMaxDepth(root);
        //res-1的原因：res代表的路径上的节点数，直径表示的是边数
        return res-1;
    }

    //计算根节点的深度，在计算根节点深度的过程中会遍历所有的节点
    //统计所有节点的左子树深度和右子树深度
    //直径：可以理解为当前节点的左子树的深度+右子树的深度+1（当前节点）
    private int getMaxDepth (TreeNode root){
        if (root==null){
            return 0;
        }

        int leftDepth = getMaxDepth(root.left);
        int rightDepth = getMaxDepth(root.right);

        res = Math.max(res,(leftDepth+rightDepth)+1);

        return Math.max(leftDepth,rightDepth)+1;

    }

    private int getMaxDepth2(TreeNode root){
        if (root==null){
            return 0;
        }

        int leftMaxDepth  = getMaxDepth2(root.left);
        int rightMaxDepth = getMaxDepth2(root.right);

        res= Math.max(res,leftMaxDepth+rightMaxDepth+1);

        int currMaxDepth = Math.max(leftMaxDepth,rightMaxDepth)+1;

        return currMaxDepth;
    }
}
